|
In the mathematical subfield of numerical analysis, numerical stability is a generally desirable property of numerical algorithms. The precise definition of stability depends on the context. One is numerical linear algebra and the other is algorithms for solving ordinary and partial differential equations by discrete approximation. In numerical linear algebra the principal concern is instabilities caused by proximity to singularities of various kinds, such as very small or nearly colliding eigenvalues. On the other hand, in numerical algorithms for differential equations the concern is the growth of round-off errors and/or initially small fluctuations in initial data which might cause a large deviation of final answer from the exact solution. Some numerical algorithms may damp out the small fluctuations (errors) in the input data; others might magnify such errors. Calculations that can be proven not to magnify approximation errors are called ''numerically stable''. One of the common tasks of numerical analysis is to try to select algorithms which are ''robust'' – that is to say, do not produce a wildly different result for very small change in the input data. An opposite phenomenon is instability. Typically, an algorithm involves an approximate method, and in some cases one could prove that the algorithm would approach the right solution in some limit. Even in this case, there is no guarantee that it would converge to the correct solution, because the floating-point round-off or truncation errors can be magnified, instead of damped, causing the deviation from the exact solution to grow exponentially. ==Stability in numerical linear algebra== There are different ways to formalize the concept of stability. The following definitions of forward, backward, and mixed stability are often used in numerical linear algebra. Consider the problem to be solved by the numerical algorithm as a function mapping the data to the solution . The result of the algorithm, say *, will usually deviate from the "true" solution . The main causes of error are round-off error and truncation error. The ''forward error'' of the algorithm is the difference between the result and the solution; in this case, . The ''backward error'' is the smallest Δ such that ; in other words, the backward error tells us what problem the algorithm actually solved. The forward and backward error are related by the condition number: the forward error is at most as big in magnitude as the condition number multiplied by the magnitude of the backward error. In many cases, it is more natural to consider the relative error : instead of the absolute error Δ. The algorithm is said to be ''backward stable'' if the backward error is small for all inputs . Of course, "small" is a relative term and its definition will depend on the context. Often, we want the error to be of the same order as, or perhaps only a few orders of magnitude bigger than, the unit round-off. The usual definition of numerical stability uses a more general concept, called ''mixed stability'', which combines the forward error and the backward error. An algorithm is stable in this sense if it solves a nearby problem approximately, i.e., if there exists a Δ such that both Δ is small and is small. Hence, a backward stable algorithm is always stable. An algorithm is ''forward stable'' if its forward error divided by the condition number of the problem is small. This means that an algorithm is forward stable if it has a forward error of magnitude similar to some backward stable algorithm. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Numerical stability」の詳細全文を読む スポンサード リンク
|